package top.lyc829.leetcode.test;

import java.util.*;


class Node {
    public int val = 0;
    public Node next = null;

    public Node() {

    }

    public Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }
}

public class MyNode {

    private Node merge(Node node1, Node node2) {

        if (node1 == null) {
            return node2;
        }
        if (node2 == null) {
            return node1;
        }

        Node head = null;
        Node first = null;

        while(node1 != null && node2 != null) {

            if (head == null) {
                if (node1.val < node2.val) {
                    head = node1;
                    first = head;
                    node1 = node1.next;
                } else {
                    head = node2;
                    first = head;
                    node2 = node2.next;
                }
            } else {
                if (node1.val < node2.val) {
                    head.next = node1;
                    node1 = node1.next;
                    head = head.next;
                } else {
                    head.next = node2;
                    node2 = node2.next;
                    head = head.next;
                }
            }
        }
        head.next = node1 == null ? node2 : node1;

        return first;
    }


    private void print(Node node) {
        if (node == null) {
            System.out.println("null...");
        } else {
            while(node != null) {
                System.out.print(node.val + " ");
                node = node.next;
            }
            System.out.println();
        }
    }


    public static void main(String[] args) {

        Node node1 = new Node(1, new Node(5, new Node(9, null)));

        Node node2 = new Node(2, new Node(4, new Node(6, new Node(10, null))));

        MyNode myNode = new MyNode();
        Node head = myNode.merge(node1, node2);

        myNode.print(head);


    }

}